<!DOCTYPE html>
        <html>
        <head>
            <meta charset="UTF-8">
            <title>RAFT&#x77e5;&#x8bc6;</title>
            <style>
/* From extension vscode.github */
/*---------------------------------------------------------------------------------------------
 *  Copyright (c) Microsoft Corporation. All rights reserved.
 *  Licensed under the MIT License. See License.txt in the project root for license information.
 *--------------------------------------------------------------------------------------------*/

.vscode-dark img[src$=\#gh-light-mode-only],
.vscode-light img[src$=\#gh-dark-mode-only],
.vscode-high-contrast:not(.vscode-high-contrast-light) img[src$=\#gh-light-mode-only],
.vscode-high-contrast-light img[src$=\#gh-dark-mode-only] {
	display: none;
}

</style>
            
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item {
    list-style-type: none;
}

.task-list-item-checkbox {
    margin-left: -20px;
    vertical-align: middle;
    pointer-events: none;
}
</style>
<style>
:root {
  --color-note: #0969da;
  --color-tip: #1a7f37;
  --color-warning: #9a6700;
  --color-severe: #bc4c00;
  --color-caution: #d1242f;
  --color-important: #8250df;
}

</style>
<style>
@media (prefers-color-scheme: dark) {
  :root {
    --color-note: #2f81f7;
    --color-tip: #3fb950;
    --color-warning: #d29922;
    --color-severe: #db6d28;
    --color-caution: #f85149;
    --color-important: #a371f7;
  }
}

</style>
<style>
.markdown-alert {
  padding: 0.5rem 1rem;
  margin-bottom: 16px;
  color: inherit;
  border-left: .25em solid #888;
}

.markdown-alert>:first-child {
  margin-top: 0
}

.markdown-alert>:last-child {
  margin-bottom: 0
}

.markdown-alert .markdown-alert-title {
  display: flex;
  font-weight: 500;
  align-items: center;
  line-height: 1
}

.markdown-alert .markdown-alert-title .octicon {
  margin-right: 0.5rem;
  display: inline-block;
  overflow: visible !important;
  vertical-align: text-bottom;
  fill: currentColor;
}

.markdown-alert.markdown-alert-note {
  border-left-color: var(--color-note);
}

.markdown-alert.markdown-alert-note .markdown-alert-title {
  color: var(--color-note);
}

.markdown-alert.markdown-alert-important {
  border-left-color: var(--color-important);
}

.markdown-alert.markdown-alert-important .markdown-alert-title {
  color: var(--color-important);
}

.markdown-alert.markdown-alert-warning {
  border-left-color: var(--color-warning);
}

.markdown-alert.markdown-alert-warning .markdown-alert-title {
  color: var(--color-warning);
}

.markdown-alert.markdown-alert-tip {
  border-left-color: var(--color-tip);
}

.markdown-alert.markdown-alert-tip .markdown-alert-title {
  color: var(--color-tip);
}

.markdown-alert.markdown-alert-caution {
  border-left-color: var(--color-caution);
}

.markdown-alert.markdown-alert-caution .markdown-alert-title {
  color: var(--color-caution);
}

</style>
        
        </head>
        <body class="vscode-body vscode-light">
            <h2 id="raft知识">RAFT知识</h2>
<h3 id="共识">共识</h3>
<p>共识涉及多个服务器对状态机状态（对本项目而言就是上层的k-v数据库）达成一致。一旦他们对状态机状态做出决定，这个决定就是最终决定（已经被集群共识的值可以保证后面不会被覆盖，Raft的安全性）。</p>
<p>实际使用系统中的共识算法一般满足以下特性：</p>
<ol>
<li><strong>在非拜占庭条件下保证共识的一致性：</strong>：非拜占庭条件就是可信的网络条件，即与你通信的节点的信息都是真实的，不存在欺骗；</li>
<li>**在多数节点存活时，保持可用性：**多数节点指的是配置文件中所有节点的多数，而不是存货节点的多数；</li>
<li>**不依赖于绝对时间：**Raft用自定的Term（任期）作为逻辑时钟来代替绝对时间；</li>
<li><strong>在多数节点达成一致后，就返回结果，而不受个别慢节点的影响</strong></li>
</ol>
<h3 id="raft中的一些重要概念">Raft中的一些重要概念</h3>
<p>状态机：raft的上层应用，可以是k-v数据库（本项目）</p>
<p><strong>日志log、entry：</strong></p>
<ul>
<li>
<p>日志log：raft保存的外部命令是以日志保存，而Raft算法可以让多个节点的上层状态机保持一致的关键是让各个节点的日志 保持一致，日志中保存客户端发送来的命令，上层的状态机根据日志执行命令，那么日志一致，自然上层的状态机就是一致的。</p>
</li>
<li>
<p>entry：日志有很多，可以看成一个连续的数组，而其中的的一个称为entry；</p>
</li>
</ul>
<p>**提交日志commit：**raft保存日志后，需要经过复制同步后，才能真正应用到上层状态机，这个应用过程称为提交；</p>
<p>**节点角色：**raft角色分为三个角色，跟随者follower、候选者Candidate、领导者leader；</p>
<p><strong>选举过程：</strong></p>
<ol>
<li>跟随者follower在任期内没有收到领导者的心跳消息后，就会认为领导者leader已经失效，然后就会将自己的角色变为候选者Candidate；</li>
<li>一旦成为候选者Candidate，该节点就会启动一个新的选举周期，增加其任期号并向集群中的其他节点发送请求选票消息；如果 Candidate获得集群中大多数节点的选票，则会成为领导者，反之，如果未赢得选举或收到来自另一个节点的合法领导者消息，他就会回退到跟随者follower状态；</li>
<li>领导者leader会周期性的发送心跳消息。这些消息不仅可以用于日志复制，还能防止其他节点发起新的选举；领导者负责接收和处理客户端的所有请求，并通过将日志条目复制到跟随者来确保日志的一致性； 如果领导者在某一任期内由于网络问题、崩溃等原因无法继续发送心跳消息，跟随者将在选举超时后开始新的选举周期；</li>
</ol>
<p>选举状态机如下图所示
<img src="file:////home/sally/worksapce/raft_-kv_-stroe/src/raft/image.png" alt="alt text"></p>
<p>**Term任期：**Raft将Term作为内部的逻辑时钟，使用Term的对比来比较日志、身份、心跳的新旧而不是用绝对时间。任期是连续的数字，并且这个任期肯定是集群的领导者的任期；Term会在follower发起选举（成为Candidate从而试图成为Leader ）的时候加1，如果顺利当选了，则任期就是当前数字，如果集群中所以的候选者都没有当选（即没有超过半数的选票），那么选举超时之后又会开始另一个Term（Term递增）的选举。</p>
<p><strong>RATF是怎样保证一个Term内只有一个Leader的呢，通过以下机制来保证：</strong></p>
<ol>
<li>单次投票原则：一个follower只能投票一次；</li>
<li>大多数原则：候选人必须取得⌊N/2⌋ + 1的选票才能成为领导者；</li>
<li>随机的选择超时时间：通过这个机制可以保证，在新的选举周期开始时，通常会有一个节点比其他节点稍早发起选举请求，增加它赢得选举的机会，减少选票分裂的可能性。</li>
</ol>
<p><strong>故障恢复时：分角色会有不同的动作</strong></p>
<ol>
<li>leader、Candidate：会对比自己的Term和当前接收到的Term，如果自己的Term小于接收的则说明自己过期了，则会回退到follower并更新term到较大的那个Term；</li>
<li>follower：更新Term信息到较大的那个Term；</li>
</ol>
<p><strong>安全性：</strong></p>
<ul>
<li>Election Safety ：每个term最多只会有一个 leader；集群同时最多只会有一个可以读写的leader。</li>
<li>Leader Append-Only ：leader 的日志是只增的。</li>
<li>Log Matching ：如果两个节点的日志中有两个entry有相同的index和term，那么它们就是相同的entry。</li>
<li>Leader Completeness ：一旦一个操作被提交了，那么在之后的term中，该操作都会存在于日志中。</li>
<li>State Machine Safety ：状态机一致性，一旦一个节点应用了某个 index 的 entry 到状态机，那么其他所有节点应用的该 index 的操作都是一致的。</li>
</ul>
<p><strong>心跳的实现是使用AppendEntry来完成的，同时AppendEntry还具有两个作用：</strong></p>
<ol>
<li>携带日志entry及其辅助信息，以控制日志的同步和日志向状态机提交；</li>
<li>通告leader的index和Term等关键信息，以便follower确定自己是否已经过期，或者当前一个leader从故障中恢复时，知道自己已不是leader，从而回退到follwoer，并更新自己的日志；</li>
</ol>
<p><strong>日志同步的过程：</strong></p>
<ol>
<li>首先我们需要知道，leader通过AppendEntryRPC向follower发送日志，并且leader发送的日志并不是系统运行以来的所有日志，这样会导致大量的开销，leader发送的日志是是包含从前一个日志条目的索引prevLogIndex和任期号prevLogTerm到当前任期的日志</li>
<li>当follower收到这个日志之后，它会检查自己本地日志中是否存在与prevLogIndex和prevLogTerm匹配的条目。如果匹配成功，跟随者就会将新的日志条目追加到自己的日志中。</li>
<li>如果不匹配，则follower则会拒绝这个AppendEntryRPC并返回false给领导者，如果leader收到了false，则说明不匹配，那么他就会发送倒数第二个任期的包含prevLogIndex和prevLogTerm的日志给follower，如果匹配就会开始同步，如果不匹配，则又拒绝，然后leader发倒数第三个任期的日志给follower，循环往复，直到匹配为止；</li>
</ol>

            
            
        </body>
        </html>